package com.johann.classify;
// 动态规划算法
// 01背包问题
// 物品编号 物品重量 物品价值
//    0         1      15
//    1         2      20
//    2         3      30
//
// 构造一个二维的dp[i][j]数组，
// 背包的编号为i
// 背包的重量为j
// 背包的价值为dp[][]
// dp[i][j] 表示[0,i]物品任取放入容量为j的背包中
// 两种情况：
// 第i个物品不放入，dp[i][j] = dp[i-1][j];
// 第i个物品放入，dp[i][j] = dp[i-1][j-weight(i)]+value(i);

//     0  1          2          3
//  0  0  (0,15)    (0,15)    (0,15)
//  1  0  (15,0)    (15,20)   (15,35)
//  2  0  (15,0)     (20,0)   (30,35)

//     0  1          2          3
//  0  0  15        15          15
//  1  0  15        20          35
//  2  0  15        20          35
public class DynamicPlan {
    // k: weight value: value
    public int maxValue(int[] weight,int[] value,int pack){
        // 物品数
        int len = weight.length;
        // 构造两个数组
        // 第一个数组存储重量
        int[] zl = new int[len+1];
        // 第二个数组存储价值
        int[] jz = new int[len+1];
        // index的值默认是0 ，index为1
        for (int i = 1; i <= len; i++) {
            zl[i]=weight[i-1];  // 0 1  2  3
            jz[i]=value[i-1];   // 0 15 25 30
        }
        // 初始化dp数组
        int[][] dp = new int[len+1][pack+1];
        dp[0][0]=0;
        //物品
        for (int i = 1; i <=len ; i++) {
            //背包
            for (int j = 0; j <=pack ; j++) {
                //背包的承载量小于第i个物品的重量
                if(j<zl[i]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]= Math.max(dp[i-1][j],dp[i-1][j-zl[i]]+jz[i]);
                }
            }
        }

        return dp[len][pack];
    }


    public static void main(String[] args) {
        System.out.println(new DynamicPlan().maxValue(new int[]{1, 2, 3}, new int[]{15, 25, 30}, 3));
    }

}
